package com.lark.algorithm.train.onChapter.linkedList;

import java.util.HashSet;
import java.util.Set;

/**
 * @author btmood
 * @version 1.0
 * @apiNote
 *
 * 给你一个链表的头节点 head ，判断链表中是否有环。
 *
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
 *
 * 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：head = [3,2,0,-4], pos = 1
 * 输出：true
 * 解释：链表中有一个环，其尾部连接到第二个节点。
 * 示例 2：
 *
 *
 *
 * 输入：head = [1,2], pos = 0
 * 输出：true
 * 解释：链表中有一个环，其尾部连接到第一个节点。
 * 示例 3：
 *
 *
 *
 * 输入：head = [1], pos = -1
 * 输出：false
 * 解释：链表中没有环。
 *
 *
 * 提示：
 *
 * 链表中节点的数目范围是 [0, 104]
 * -105 <= Node.val <= 105
 * pos 为 -1 或者链表中的一个 有效索引 。
 *
 *
 * 进阶：你能用 O(1)（即，常量）内存解决此问题吗？
 * @since 2024-05-21 15:27
 */
public class D20240521Q141_环形链表 {

    // 错误的
    // 判断链表中有没有环
    // 返回是否有
    public boolean hasCycle(ListNode head) {
        // 这个不是最小问题，如果是环形链表就没有null了
        if (head == null) {
            return false;
        }
        boolean f1 = hasCycle(head.next);
        if (f1) {
            return true;
        }
        ListNode cur = head.next;
        while (cur != null) {
            if (cur.next == head) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    // 递归
    public boolean hasCycle2(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        if (head.next == head) {
            return true;
        }
        ListNode nextNode = head.next;
        head.next = head;
        return hasCycle2(nextNode);
    }

    // 哈希
    public boolean hasCycle3(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head)) {
                return true;
            }
            set.add(head);
            head = head.next;
        }
        return false;
    }

    public boolean hasCycle4(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;

        while (slow != null && fast != null && fast.next != null) {
            if (slow == fast) {
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }

    // 快慢指针优化
    public boolean hasCycle5(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    public static class  ListNode {
        int val;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
        ListNode next;

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            ListNode cur = next;
            sb.append(val);
            while (cur != null) {
                sb.append("=>");
                sb.append(cur.val);
                cur = cur.next;
            }
            return sb.toString();
        }
    }
}
